In typical public key cryptography systems, digital signature key pairs, having a private key and public key, are often used to authenticate a digital signature of a subscriber using a software application in order to confirm the identity of the sender of the message. A subscriber may generally be for example a network computer node, a software application or user in the security system. In addition to digital signature key pairs, encryption key pairs are also generally used to encrypt the data being sent from one subscriber to another subscriber within the computer network. Certificates are typically generated by a trusted certification authority for the public keys of the private/public key pair to certify that the keys are genuinely owned by a named subscriber. Standards, such as ISO 9594-8 available from the International Organization for Standardization, define typical certificate content.
In a network community, there may be a multitude of different certification authorities and many subscribers. Generally, each subscriber stores a certification authority public key to verify that a trusted certification authority issued the certificate. A public key certificate typically includes a user public key which is bound by the signature of the certification authority to the subscriber name, and other data including expiry data indicating the expiration date or period for the public key certificate. Each sender (subscriber) has a copy of its own certificate. To send an encrypted message, a sender may access a directory, such as an onboard client cache memory or other certificate storage medium to get a copy of an encryption certificate for a specified receiver. When receiving digitally signed data, a receiver obtains a signature verification certificate and determines from the obtained certificate whether the sender has a valid signature. Generally, for a certificate to be considered valid, the digital signature must be valid and there must be no existing expiration or revocation of the certificate by an associated certification authority. Hence, subscribers typically serve as certificate validation units and validate certificates before encrypting information to other subscribers. Similarly, the subscribers also need to verify signature verification certificates before using a public key to validate a subscriber's signature.
In computer network systems that employ cryptography, the certification authority, also referred to herein as the certificate issuing unit, typically issues certificates for subscribers that use the associated certification authority as the primary trusted server. Alternatively, in some systems a trusted subscriber may play the role of a CA in generating and signing certificates of other subscribers. In larger networks, the trust relationships between the certification authorities typically involve multiple certification authorities. Trust relationships between certification authorities determine how certificates issued by one certification authority may be utilized or verified by entities certified by distinct certification authorities such as those in other networks. Since public key certificates provide a mechanism for obtaining authenticated public keys, provided the verifier has a trusted verification public key of the certification authority which signed the certificate, trusted paths may be established and maintained among the certification authorities and hence subscribers in large computer networks. In the case of multiple certification authorities, a certificate verification unit, such as a subscriber, may wish to obtain an authentic public key by verifying a certificate signed by a certification authority other than one for which it originally possesses a trusted public key. In this case, the verifier may still verify a certificate signed by other certification authorities provided a chain of certificates can be constructed which corresponds to an unbroken chain of trust from the certification authority public key which the verification unit does trust, to the public key it wishes to obtain trust in.
Conventional cryptographic systems, such as many public key cryptography systems, typically use a distributed directory where all certificates and certificate revocation lists are duplicated so each subscriber in a system can access the directory to perform validation. Certificate chains correspond to directed trust paths, also known as certification paths, such as trust relationships among certification authorities where at least one certification authority (CA) has certified another certification authority. A certificate containing the public key of a certification authority is called a CA-certificate. A CA-certificate resulting from one CA certifying another CA is called a cross-certificate, and the process of creating such a certificate is called cross-certification. In this case the CA which signs the certificate is different from the CA whose public key appears within the certificate. A CA-certificate may be either a cross-certificate or a self-signed certificate (where the latter is a CA-certificate signed by the same CA whose public key is within the certificate). One way certification occurs where one certification authority certifies another certification authority but reciprocal certification does not occur. Where a pair of certification authorities certify each other, this is referred to as mutual cross-certification. In this case, the two corresponding cross-certificates are called a cross-certificate pair.
To ensure validity of a subscriber's public key, so that a subscriber may receive or send information along a fully trusted path, the goal for a verification unit is to find a sequence of certificates corresponding to a certification path starting at the certification authority whose public key the subscriber trusts a priori, and ending at a target certification authority which has signed the certificate of the public key to be verified. If the search for trusted paths is carried out using conventional search techniques, such as breadth first or depth first techniques as known in the art (see for example page 215-218 and 239-244 in "Data Structures and Algorithms", by Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, published in 1983 by Addison-Wesley, Reading, Mass., incorporated herein by reference), then a problem arises by way of reduced system performance when large numbers of certification authorities are in the community of interest, and many different combinations of links among certification authorities in various networks (or the same network) exist. In such systems, a verification unit may spend valuable processing time verifying all combinations of links to determine whether a trusted path has been maintained with the certification authority of the verifying verification unit and the certificate issuing unit that issued the target certificate. An inefficiency results when many of the steps involved in an exhaustive search which explores a large number of network nodes, for example in a breadth-first search, end up leading to untrusted or non-existent paths, and therefore unnecessarily consumed computational effort. For example, the validation unit typically has to find the certification paths every time a signed electronic document is received or any time an encryption occurs; checking a large number of possible certification authority paths can be unnecessary and can take long periods of time thereby decreasing the system performance. In large systems, the performance may be so impeded as to render the validation unit impractical.
Hierarchical chain trust structures with one way and/or mutual cross-certification among certificate issuing units typically have verification units verify in the following manner. Each entity or verification unit starts with a trusted public key, for example the public key of the certificate issuing unit which created its own certificate (parent CA). The shortest trust chain from any entity is a path in the tree which travels upward from the parent to a least common ancestor of the entity and a target entity, and then onwards back down to the target entity. However, substantial entity resources can be expended in analyzing all of the possible certification links where a network contains a large number of certification authorities.
Referring to FIG. 1, an example of another known certificate issuing unit trust structure is shown, sometimes referred to as a distributed trust arrangement. The solid lines represent trust relationships and the arrows on the solid lines represent a signed certificate. For example, CA1 has certified the public key certificate of CA2. Also, mutual cross-certification exists between CA3 and CA4. The dashed lines from subscribers A and B represent each subscriber holding a copy of the CA public key and thereby trusting the CA implicitly. If subscriber A in possession of public key P5 of CA5 wishes to verify the certificate of the subscriber B signed by CA3 and thereby obtain trust in the public key (PB) of B, a directed path (CA5, CA4, CA3) exists. However, the subscriber A in a conventional rooted hierarchy based system, in which subscribers trust the public key of the root CA in the hierarchy, may be provided with the chain by another subscriber. This chain is from the root CA to a subscriber unit and may or may not be the shortest path. However, in distributed trust systems the subscriber A is not typically provided with the chain, and the subscriber must attempt to construct the chain, possibly every time a document is sent or encrypted. For example, subscriber A examines the data stored under its own CA entry from the common directory and evaluates all CA cross-certificates. Subscriber A then typically evaluates each CA entry of the cross-certified CA's in the common directory and obtains the certificates for each of the listed CA's. The subscriber A continues to expand all paths to each node (CA) encountered until it finds the certificate of the destination CA it is seeking. If all subscribers are performing this operation continuously, system performance can suffer and additional expense can be incurred.
Routing tables are known in communication systems to facilitate routing of information among nodes. However, such known routing systems do not typically determine trust path construction among trusted certificate issuing units nor provide certificate validation information for certificate validation units. Also, while methods for determining certificate revocation status have been proposed involving sending queries or certification information to a certificate status checking unit, to date such systems typically involve only one CA and do not address issues related to certificate chain construction as the chain is fixed or known.
Consequently there exists a need for a method and apparatus for determining the validity of a certificate in a communication system employing trusted paths which addresses these problems.